package ds.sort;

import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;

import ds.heap.Heap;
import ds.linklist.sorted.SortedLinkList;
import ds.util.GeneralApp;

public class Sort {
	
	// ############  平方阶 O（N^2）  ############

	/**
	 * 冒泡排序 outer从[length-1]（数组最后一个元素）开始，--，到[0]（数组第一个元素）【时】-结束
	 * 内层循环从[0]开始，++，到[outer]【时】结束
	 * 
	 * 比较次数：N*N/2 交换次数：N*N/4
	 * 
	 * 时间：O（N^2）
	 **/
	public static int[] bubbleSort(int[] a) {
		for (int i = a.length - 1; i > 0; i--) {
			for (int j = 0; j < i; j++) {
				if (a[j] > a[j + 1])
					swap(a, j, j + 1);
			}
		}
		return a;
	}

	/**
	 * 选择排序 outer从[0]开始，到[length-1]（数组最后一个元素）时结束，++
	 * 内层循环从[outer+1]开始，++，到[length]时结束
	 * 最小指针初始化为[outer]
	 * 
	 * 比较次数：N*N/2 交换次数：N/2 -- 降到了最低
	 * 
	 * 时间：O（N^2），N值比较小时、比冒泡快很多
	 * */
	public static int[] selectSort(int[] a) {
		for (int k = 0; k < a.length - 1; k++) {
			int minIndex = k;
			for (int i = k + 1; i < a.length; i++) {
				if (a[i] < a[minIndex]) {
					minIndex = i;
				}
			}
			if (minIndex != k) {
				swap(a, minIndex, k);
			}
		}
		return a;
	}

	/**
	 * 插入排序(h=1 的 增量排序) 外层循环从[h]（其实是从增量[h]）开始，++，到[length]结束
	 * 内层循环从下标[outer]开始，--h，到[0(以后)]结束
	 * 
	 * 比较次数：N*N/4 复制次数：大致等于比较次数
	 * 
	 * 时间：
	 *    有序、基本有序 O(N)
	 *    随机无序、倒序 O（N^2），一般认为还是O(N*N)
	 * 
	 **/
	public static int[] insertSort(int[] a) {
		for (int i = 1; i < a.length; i++) {
			int temp = a[i];
			int k;
			for (k = i - 1; k >= 0 && a[k] > temp; k--) {
				a[k + 1] = a[k];
			}
			a[k + 1] = temp;

			// int k = i;
			// while(k > 0 && a[k-1]>temp)
			// {
			// a[k] = a[k-1];
			// k--;
			// }
			// a[k] = temp;
		}
		return a;
	}

	/**
	 * 表插入排序
	 * 
	 * 借用了有序链表，明显减少了复制的次数（N*N -> 2*N），系统内存开销增大
	 */
	public static int[] tableInsertSort(int[] a) {
		SortedLinkList sll = new SortedLinkList();
		for (int i = 0; i < a.length; i++) {
			sll.insert(a[i]);
		}
		for (int i = 0; i < a.length; i++) {
			a[i] = sll.delete().getData();
		}
		return a;
	}
	
	
	
	
	// ############  线性对数阶 O（N*log2N）############

	/**
	 * 归并排序 O（N*log2N）
	 * 
	 * 稳定的，并且最好最坏情况时间复杂度都是 O（N*log2N）
	 * 
	 */
	public static int[] mergeSort(int[] a) {
		recMergeSort(a, 0, a.length - 1);
		return a;
	}

	private static void recMergeSort(int[] a, int lowerBound, int upperBound) {
		if (lowerBound == upperBound)
			return;
		else { // “归”
			int mid = (lowerBound + upperBound) / 2;
			recMergeSort(a, lowerBound, mid); // 先下
			recMergeSort(a, mid + 1, upperBound); // 后上

			// “并”：
			// merge(a, lowerBound, mid+1, upperBound); // 再合并
			int temp[] = new int[upperBound - lowerBound + 1];

			int lowerIndex = lowerBound;
			int upperIndex = mid + 1;
			int tempIndex = 0;

			while (lowerIndex < mid + 1 && upperIndex < upperBound + 1) {
				if (a[lowerIndex] < a[upperIndex])
					temp[tempIndex++] = a[lowerIndex++];
				else
					temp[tempIndex++] = a[upperIndex++];
			}
			while (lowerIndex < mid + 1) {
				temp[tempIndex++] = a[lowerIndex++];
			}
			while (upperIndex < upperBound + 1) {
				temp[tempIndex++] = a[upperIndex++];
			}
			for (int i = 0; i < temp.length; i++) {
				a[lowerBound + i] = temp[i];
			}
		}
	}

	/**
	 *  快速排序， O（N*log2N）
	 *  
	 *  其实是冒泡法的改进，它通过一次交换能消除多个逆序，这样可以减少逆序时所消耗的扫描和数据交换次数
	 *  在“最优”的情况（每次划分序列时，都可以平均分成两个子串）下，时间复杂度为O（N*log2N）
	 *  在“最差”情况下（每次划分序列时，一串为空，另一串为m-1）
	 *  快速排序的表现跟“枢纽”的选取关系密切
	 * 
	 *  找“枢纽”来“划分”
	 *  以递归来分冶
	 *  
	 *  划分：把数据分为两组，使所有关键字大于特定值（称为“枢纽”）的数据项在一组，使所有关键字小于特定值的数据项在另一组
	 *  由两个循环构成的划分算法
	 *  
	 *  ps：“快排不快”的情况
	 *  若原数据为有序，并且选择的枢纽值为第一个数时，那在分块时会将一个第一个数前面的数（也就是没有）
	 *  分为一块，将除第一个数的所有数分成了另一块。这样一来，每一次分块都只减少了一个值，而每次分块的时间为
	 *  O（N），所以总时间为O（N^2）；可以在取枢纽值时，用“三数据项取中”法
	 *  
	 * */
	public static int[] quickSort(int[] a) {

		recQuickSort(a, 0, a.length - 1);

		return a;
	}

	private static void recQuickSort(int[] a, int left, int right) {
		if (right - left <= 0)
			return;
		else {
			// int pivot = a[right];
			int partition = findPivotAndPartitionWithIt(a, left, right);
			recQuickSort(a, left, partition - 1);
			recQuickSort(a, partition + 1, right);
		}
	}

	private static int findPivotAndPartitionWithIt(int[] a, int left, int right) {
		// 直接把最右边的当枢纽 // TODO，可以用“三数据项取中”法
		int pivotIndex = right;
		int pivot = a[pivotIndex]; 
		
		int leftPtr = left - 1; // 左指针
		int rightPtr = right;  // 右指针
		while (true) {
			while (a[++leftPtr] < pivot) // 左指针停于>=pivot的值上
				// 由于把枢纽选在的最右端，所以可以不检测边界
				;
			while (rightPtr > 0 && a[--rightPtr] > pivot) // 右指针停于<=pivot的值上
				;
			if (leftPtr < rightPtr) { // 如果“左指针还位于右指针左边“
				swap(a, leftPtr, rightPtr); // 交换！
			} else { // 否则，跳出循环，此时左指针必然停在这样的点上：它的左边都<=pivot，右边都>=pivot
				break;
			}
		}
		// 从循环跳出后，左指针的位置，就是pivot值排序后的最终位置！
		swap(a, leftPtr, pivotIndex);
		return leftPtr;
	}

	/**
	 * 堆排序（表插入排序改进结构板）， O（N*log2N）
	 * 
	 *  */
	public static int[] heapSort(int[] a) {
		Heap heap = new Heap(a.length);
		for (int i = 0; i < a.length; i++) {
			heap.insert(a[i]);
		}

		a = new int[a.length];
		for (int i = 0; i < a.length; i++) {
			a[i] = heap.remove().getKey();
		}
		return a;
	}

	/**
	 *  希尔排序 O（N^（1-2））
	 * 
	 *  */
	public static int[] shellSort(int[] a) {
		int inner, outer;
		int temp;

		int h = 1;
		// find initial value of h
		while (h <= a.length / 3) {
			h = h * 3 + 1;
		}

		while (h > 0) {
			for (outer = h; outer < a.length; outer++) {
				temp = a[outer];
				inner = outer;

				// 第一次比较肯定只有两个，之后的可能是3个以上
				while (inner > h - 1 && a[inner - h] >= temp) {
					a[inner] = a[inner - h];
					inner -= h;
				}
				a[inner] = temp;
			}
			h = (h - 1) / 3;
		}
		return a;
	}

	/** 希尔排序，自己默写+带注释版 */
	public static int[] shellSort2(int[] a) {
		// 找h
		int h = 1;
		while (h <= a.length / 3) { // 选择间隔序列有一个绝对的条件：逐渐减小的间隔最后一定要等于 "1"
			h = 3 * h + 1; // Knuth 间隔序列：h=3*h+1，间隔序列的数字互质通常被认为很重要，也就是说，间隔序列的所有数没有除了1以外的公约数
		}

		while (h > 0) {
			// outer从h开始
			for (int outer = 0 + h; outer < a.length; outer++) { // 相当于“时分复用”地进行着h个”并发“的插入排序
				int temp = a[outer]; // 可以想象成“移走”了，这个位置“空”了出来
				int inner;
				// inner从outer-h开始，比前一个位置大的来“填补”空位，如果没有大的了，则把temp“放回”
				for (inner = outer - h; inner >= 0; inner -= h) { // 前面的都是有序的
					if (a[inner] > temp) {
						a[inner + h] = a[inner];
					} else {
						break; // 此时的inner+h就是temp放回的位置！
					}
				}
				a[inner + h] = temp;
			}
			h = (h - 1) / 3;
		}
		return a;
	}

	private static void swap(int[] a, int index1, int index2) {
		int temp = a[index1];
		a[index1] = a[index2];
		a[index2] = temp;
	}
	
	public static void sleepSort(final int[] a) {
		for (int i = 0; i < a.length; i++) {
			final int index = i;
			new Thread(new Runnable(){
				public void run() {
					try {
						Thread.sleep(a[index]);
					} catch (InterruptedException e) {
						e.printStackTrace();
					}
					System.out.println(a[index]);
				}
			}).start();
		}
	}
	
	public static void main(String[] args) {
		sleepSort(new int[]{45,23,1,4,6,7,89,0});
	}

}

/*
 * class SortApp1 { public static void main(String args) { int[] a =
 * GeneralApp.randomArray(50000, 10000); long start =
 * System.currentTimeMillis(); Sort.bubbleSort(a); long end =
 * System.currentTimeMillis(); System.out.println("time:" + (end - start) +
 * "ms");
 * 
 * int[] b = GeneralApp.randomArray(50000, 10000); start =
 * System.currentTimeMillis(); Sort.selectSort(b); end =
 * System.currentTimeMillis(); System.out.println("time:" + (end - start) +
 * "ms");
 * 
 * int[] c = GeneralApp.randomArray(50000, 10000); start =
 * System.currentTimeMillis(); Sort.insertSort(c); end =
 * System.currentTimeMillis(); System.out.println("time:" + (end - start) +
 * "ms");
 * 
 * int[] d = GeneralApp.randomArray(50000, 10000); start =
 * System.currentTimeMillis(); Sort.tableInsertSort(d); end =
 * System.currentTimeMillis(); System.out.println("time:" + (end - start) +
 * "ms");
 * 
 * int[] e = GeneralApp.randomArray(50000, 10000); start =
 * System.currentTimeMillis(); Sort.mergeSort(e); end =
 * System.currentTimeMillis(); System.out.println("time:" + (end - start) +
 * "ms");
 * 
 * int[] f = GeneralApp.randomArray(50000, 10000); start =
 * System.currentTimeMillis(); Sort.shellSort(f); end =
 * System.currentTimeMillis(); System.out.println("time:" + (end - start) +
 * "ms");
 * 
 * int[] g = GeneralApp.randomArray(50000, 10000); start =
 * System.currentTimeMillis(); Sort.quickSort(g); end =
 * System.currentTimeMillis(); System.out.println("time:" + (end - start) +
 * "ms"); }
 * 
 * }
 */

class SortApp2 {
	public static void main(String[] args) {

		Class clz = Sort.class; // 定位类
		Class methodParameterTypes[] = new Class[1]; // 定参数个数（通过Class[?]）
		methodParameterTypes[0] = int[].class; // 定各个参数类型（给Class[]的每个元素指定具体内容）

		String[] sortNames = { "bubbleSort", "selectSort", "insertSort", "tableInsertSort", "mergeSort", "shellSort", "quickSort", "heapSort" }; // 参数名

		for (int i = 0; i < sortNames.length; i++) {
			try {
				Method sortMethod = clz.getMethod(sortNames[i], methodParameterTypes);
				// System.out.println(Modifier.toString(sortMethod.getModifiers()));
				int[] a = GeneralApp.randomArray(50000, 50000);
				long start = System.currentTimeMillis();
				// int[] result = (int[])sortMethod.invoke(null, new
				// Object[]{randomArray(100,50000)});
				sortMethod.invoke(null, new Object[] { a });
				long end = System.currentTimeMillis();

				System.out.println(sortNames[i] + ":" + (end - start) + "ms");
				// printArray(result);

			} catch (SecurityException e1) {
				e1.printStackTrace();
			} catch (NoSuchMethodException e1) {
				e1.printStackTrace();
			} catch (IllegalArgumentException e1) {
				e1.printStackTrace();
			} catch (IllegalAccessException e1) {
				e1.printStackTrace();
			} catch (InvocationTargetException e1) {
				e1.printStackTrace();
			}
		}
	}
}

class SortApp3 {
	public static void main(String[] args) {
		long t1 = System.currentTimeMillis();
		int[] a = Sort.quickSort(GeneralApp.randomArray(5000, 5000));
		System.out.println(System.currentTimeMillis() - t1);
		GeneralApp.printArray(a);

		long t2 = System.currentTimeMillis();
		a = Sort.quickSort(a);
		System.out.println(System.currentTimeMillis() - t2);
		GeneralApp.printArray(a);
	}
}